package demo2;

import java.util.*;

public class Solution {

    public int longestSemiRepetitiveSubstring(String s) {
        char[] ch = s.toCharArray();
        int ret = 1, same = 0;
        for(int left = 0, right = 1; right < ch.length; right++){
            if(ch[right] == ch[right - 1]){
                same++;
            }

            if(same > 1){
                left++;
                while(ch[left] != ch[left - 1]){
                    left++;
                }
                same = 1;
            }
            ret = Math.max(ret, right - left + 1);
        }
        return ret;
    }

    public int maximumBeauty(int[] nums, int k) {
        Arrays.sort(nums);
        int ret = 0;
        for(int left = 0, right = 0; right < nums.length; right++){
            while(nums[right] - nums[left] > k * 2){
                left++;
            }
            ret = Math.max(ret, right - left + 1);
        }
        return ret;
    }

    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length, count = 0, sum = 0, max = 0;
        for(int left = n - 1, right = n - 1; left >= 0; left--){
            sum++;
            count = count + nums[right] - nums[left];
            while(count > k){
                sum--;
                count = count - (nums[right] - nums[right - 1]) * sum;
                right--;
            }
            max = Math.max(max, sum);
        }
        return max;
    }

    public int takeCharacters(String s, int k) {
        char[] ch = s.toCharArray();
        int[] cnt = new int[3];
        for(char x : ch){
            cnt[x - 'a']++;
        }
        if(cnt[0] < k || cnt[1] < k || cnt[2] < k) { return -1;}

        int ret = 0;
        for(int left = 0, right = 0; right < ch.length; right++){
            cnt[ch[right] - 'a']--;

            while(cnt[ch[right] - 'a'] < k){
                cnt[ch[left++] - 'a']++;
            }
            ret = Math.max(ret, right - left + 1);
        }
        return ch.length - ret;
    }

    public int longestEqualSubarray(List<Integer> nums, int k) {
        int n = nums.size();
        Map<Integer, List<Integer>> pos = new HashMap<>();
        for(int i = 0; i < n; i++){
            pos.computeIfAbsent(nums.get(i), x -> new ArrayList<>()).add(i);
        }

        int ret = 0;
        for(List<Integer> tmp : pos.values()){
            for(int i = 0, j = 0; i < tmp.size(); i++){
                while(tmp.get(i) - tmp.get(j) - (i - j) > k){
                    j++;
                }
                ret = Math.max(ret, i - j + 1);
            }
        }
        return ret;
    }

    public int longestEqualSubarray2(List<Integer> nums, int k) {
        int n = nums.size();
        int ret = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        for(int i = 0, j = 0; j < n; j++){
            cnt.put(nums.get(j), cnt.getOrDefault(nums.get(j), 0) + 1);

            while(j - i + 1 - cnt.get(nums.get(i)) > k){
                cnt.put(nums.get(i), cnt.get(nums.get(i)) - 1);
                i++;
            }

            ret = Math.max(ret, cnt.get(nums.get(j)));
        }
        return ret;
    }

    public int longestEqualSubarray3(List<Integer> nums, int k) {
        int n = nums.size();
        List<Integer>[] posLists = new ArrayList[n + 1];
        Arrays.setAll(posLists, i -> new ArrayList<>());
        for(int i = 0; i < n; i++){
            int x = nums.get(i);
            posLists[x].add(i - posLists[x].size());
        }

        int ret = 0;
        for(List<Integer> pos : posLists){
            if(pos.size() <= ret){
                continue;
            }

            for(int left = 0, right = 0; right < pos.size(); right++){
                while(pos.get(right) - pos.get(left) > k){
                    left++;
                }
                ret = Math.max(ret, right - left + 1);
            }
        }
        return ret;
    }

    public int maximumWhiteTiles(int[][] tiles, int carpetLen) {
        Arrays.sort(tiles, (a, b) -> a[0] - b[0]);
        int ret = 0, cover = 0, i = 0;
        for(int[] tile : tiles){
            int l = tile[0], r = tile[1];
            cover += r - l + 1;
            while(tiles[i][1] + carpetLen - 1 < r){
                cover -= tiles[i][1] - tiles[i][0] + 1;
                i++;
            }
            int uncover = Math.max(r - carpetLen + 1 - tiles[i][0], 0);
            ret = Math.max(ret, cover - uncover);
        }
        return ret;
    }

    public int maximumWhiteTiles2(int[][] tiles, int carpetLen) {
        Arrays.sort(tiles, (o1, o2) -> o1[0] - o2[0]);
        int n = tiles.length, l = 0, r = 0, sum = 0, max = 0;
        while(l <= r && r < n){
            int leftBound = tiles[l][0], rightBound = leftBound + carpetLen - 1;
            if(tiles[r][1] <= rightBound){  //未覆盖完
                sum += tiles[r][1] - tiles[r][0] + 1;
                r++;
                max = Math.max(max, sum);
            }else{
                if(rightBound >= tiles[r][0]){  //覆盖部分
                    max = Math.max(max, sum + rightBound - tiles[r][0] + 1);
                }
                sum -= tiles[l][1] - tiles[l][0] + 1;  //调整到下个区间
                l++;
            }
        }
        return max;
    }


}
